# -*- coding: utf-8 -*-
# author: AZJ
# date: 2024/11/13
# 假如命运扼住了你的咽喉，你就去挠她的咯吱窝

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        # dp[i][j] = dp[i-1][j] + dp[i][j-1]
        # 如果grid[i][j] = 1, dp[i][j] = -1 continue
        x = len(obstacleGrid[0])
        y = len(obstacleGrid)
        dp = [[1] * x] + [[1] + [0 for _ in range(x - 1)] for _ in range(y - 1)]
        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
            return 0
        if x == 1 and 1 in obstacleGrid[0]:
            return 0
        elif x == 1:
            return 1
        if x <= 1 or y <= 1:
            if 1 in obstacleGrid or 1 in obstacleGrid[0]:
                return 0
        for i in range(y):
            for j in range(x):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                    continue
                if i == 0 and dp[i][j - 1] == 0:
                    dp[i][j] = 0
                if j == 0 and dp[i - 1][j] == 0:
                    dp[i][j] = 0
                if i >= 1 and j >= 1:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[-1][-1]



if __name__ == '__main__':
    solution = Solution()
    # print(solution.uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]]))
    print(solution.uniquePathsWithObstacles([[0,0],[1,0],[0,0]]))